// class Solution {
// public:
//     bool wordBreak(string s, vector<string>& wordDict) {
//         int m = s.size();
//         int n = wordDict.size();
//         vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
//         for (int i = 0; i <= n; i++)
//             dp[i][0] = 1;
//         for (int j = 0; j <= m; j++) {
//             for (int i = 1; i <= n; i++) {
//                 dp[i][j] = dp[i - 1][j];
//                 if (wordDict[i - 1].size() <= j) {
//                     if (dp[i][j - wordDict[i - 1].size()]) {
//                         string str = s.substr(j - wordDict[i - 1].size(),
//                                               wordDict[i - 1].size());
//                         if (str == wordDict[i - 1]) {
//                             dp[i][j] = 1;
//                             for (int l = 1; l <= n; l++)
//                                 dp[l][j] = 1;
//                         }
//                     }
//                 }
//             }
//         }
//         return dp[n][m];
//     }
// };

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = wordDict.size();
        int m = s.size();
        vector<int> dp(m + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= m; j++) {
            for (int i = 1; i <= n; i++) {
                if (wordDict[i - 1].size() <= j) {
                    if (dp[j - wordDict[i - 1].size()]) {
                        string str = s.substr(j - wordDict[i - 1].size(),
                                              wordDict[i - 1].size());
                        if (str == wordDict[i - 1]) {
                            dp[j] = 1;
                        }
                    }
                }
            }
        }
        return dp[m];
    }
};